/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * Dijkstra.java
 * ---------------------------
 *
 */
package dijkstra;

import java.util.Arrays;
import java.util.List;

import nodes.Edge;
import nodes.GraphNode;

/**
 * Java implementation of Dijkstra's shortest path algorithm.
 * <p>
 * Watch out! Untested for distances equal to Integer.MAX_VALUE.
 * 
 * @author Saverio Miroddi
 */
public class Dijkstra
{
	private static final int NODE_NOT_FOUND = -1;
	private static final int INFINITE = Integer.MAX_VALUE;
	
	public static int[] computeMinDistances(
			List<GraphNode> nodes, int startNodeIdx)
	{
		boolean[] visiteds = new boolean[nodes.size()];
		int [] distances = new int[nodes.size()];
		int[] previouses = new int[nodes.size()];
		
		setupData(startNodeIdx, nodes, visiteds, distances, previouses);
		
		while (true) {
			int currentIdx = pickSmallerNonVisited(visiteds, distances);
			
			// if no nodes found, we're done, otherwise mark the chosen
			// as visited
			if (currentIdx == NODE_NOT_FOUND) break;
			else visiteds[currentIdx] = true;
			
			GraphNode current = nodes.get(currentIdx);
			// see the distance so far from start to the current node 
			int distStartToCurrent = distances[currentIdx];

			// pick the current node's pointed nodes
			for (Edge edge : current.getEdges()) {
				int nextNodeIdx = nodes.indexOf(edge.node); // unopt
				
				/* is it short to go from the start node to the next node
				passing through the current, rather than the distance
				we already have memorized?
				*/
				int distStartToNextThroughCurr = 
					distStartToCurrent + edge.distance;
				int distStartToNext = distances[nextNodeIdx];
				
				if (distStartToNextThroughCurr < distStartToNext) {
					// if so, store the distance we got, and mark the current
					// node as the one we will go through.
					distances[nextNodeIdx] = distStartToNextThroughCurr;
					previouses[nextNodeIdx] = currentIdx;
				}				
			}
		}

		return distances;
	}
	
	private static void setupData(
			int startNodeIdx, List<GraphNode> nodes,
			boolean[] visiteds, int[] distances,  int[] previouses)
	{
		Arrays.fill(visiteds, false); // optional
		visiteds[startNodeIdx] = true;

		Arrays.fill(distances, INFINITE);

		// then we overwrite with distance 0 (startNode from itself),
		// and distance from startNode the nodes it's pointing to.
		distances[startNodeIdx] = 0;
		for (Edge edge : nodes.get(startNodeIdx).getEdges()) {
			int nextIdx = nodes.indexOf(edge.node); // unopt
			distances[nextIdx] = edge.distance;
		}

		Arrays.fill(previouses, startNodeIdx);
	}

	private static int pickSmallerNonVisited(
			boolean[] visited, int[] distances)
	{
		int currMinNode = NODE_NOT_FOUND;
		int currMinDist = INFINITE;
		
		for (int i = 0; i < visited.length; i++) {
			if (! visited[i] && distances[i] < currMinDist) {
				currMinNode = i;
				currMinDist = distances[i];
			}
		}
		
		return currMinNode;
	}
}
